// https://leetcode.cn/problems/peak-index-in-a-mountain-array/

// 题干：符合下列属性的数组 arr 称为 山脉数组 ：
//      arr.length >= 3
//      存在 i（0 < i < arr.length - 1）使得：
//      arr[0] < arr[1] < ... arr[i-1] < arr[i]
//      arr[i] > arr[i+1] > ... > arr[arr.length - 1]
//      给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
//      你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

// 示例：输入：arr = [0,1,0]
//       输出：1

// 碎语：题目数据保证是一个山脉数组，同时根据题意，判断不是两侧
//       O(logN)的说法暗示了二分查找，由此我们思考二分查找是不是真的需要数组有序
//       很明显并不是，只需要满足二分性即可

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int peakIndexInMountainArray(vector<int>& nums)
    {
        int left = 1, right = nums.size() - 2;

        while (left < right){
            int mid = left + (right - left + 1) / 2;

            if (nums[mid] > nums[mid - 1]) left = mid; // mid有可能就是山脉数组的山顶元素下标
            else right = mid - 1;
        }

        return left;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {0,5,10,2};

    int index = sol.peakIndexInMountainArray(nums);
    cout << index << endl;

    return 0;
}